Existing computer programs known as “road-mapping” programs provide digital maps, often complete with detailed road networks down to the city-street level. Typically, a user can input a location and the road-mapping program will display an on-screen map of the selected location. Several existing road-mapping products typically include the ability to calculate an “optimal route” between two locations. In other words, the user can input two locations, and the road-mapping program will compute the travel directions from the source location to the destination location. The directions are typically based on distance, travel time, and certain user preferences, such as a speed at which the user likes to drive, or the degree of scenery along the route. Computing the optimal route between locations may require significant computational time and resources.
These systems produce driving directions by computing a shortest path (or an approximation) with respect to a length function based on various measures, such as distance and travel time. However, optimal routes do not necessarily match the personal preferences of individual users. For driving directions, users may prefer alternatives to optimal (shortest or fastest) routes. These preferences may be based on better local knowledge, a bias for or against a certain route segment, or other factors, and may be unknown to the system One can deal with this issue by presenting a small number of alternative routes and hoping one of them will satisfy the user. However, alternative routes are often provided that are impractical, inefficient, look unreasonable to the user, contain unnecessary local detours, and/or are not much different than the optimal path.